package num220;

import java.util.HashMap;
import java.util.Map;

/**
 * @author : DuJiabao
 * @Project : sword-finger-offer
 * @Time : 2021/5/9 18:09
 * @Desc :
 */
public class Solution {
  public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    Map<Integer, Integer> bucket = new HashMap<>();
    int bucketSize = t + 1;

    for (int i = 0; i < nums.length; i++) {
      int key = nums[i] / bucketSize;
      if (bucket.containsKey(key))
        return true;
      Integer prevIndex = bucket.get(key - 1);
      if (prevIndex != null && Math.abs(nums[prevIndex] - nums[i]) <= t) return true;
      Integer postIndex = bucket.get(key + 1);
      if (postIndex != null && Math.abs(nums[postIndex] - nums[i]) <= t) return true;

      bucket.put(key, i);
      int removedKey = nums[i - k] / bucketSize;
      bucket.remove(removedKey);
    }
    return false;
  }

  public static void main(String[] args) {
    //int[] nums = {1, 2, 3, 1};
    //boolean res = new Solution().containsNearbyAlmostDuplicate(nums, 3, 0);
    //int[] nums = {-2147483648, 2147483647};
    //boolean res = new Solution().containsNearbyAlmostDuplicate(nums, 1, 1);
    //System.out.println(res);
  }
}
